#include <vector>
#include <string>
using namespace std;
/*
 * @lc app=leetcode.cn id=97 lang=cpp
 *
 * [97] 交错字符串
 */

// @lc code=start
class Solution {
public:

    // 采用动态规划的思想
    // dp[i][j] s1前i个和s2前j个是否可以组成s3前 i + j个
    // dp[i][j] = dp[i - 1][j] || dp[i][j - 1]
    //
    // 如果优化成一维的数组
    bool isInterleave(string s1, string s2, string s3) {
        vector<bool> dp(s2.size() + 1, false);
        if (s1.size() + s2.size() != s3.size()) return false;
        dp[0] = true; // 如果考虑滚动数组的话
        // 考虑滚动数组的本质就是考虑谁在更新, 谁还没有更新的问题
        for (int i = 0; i <= s1.size(); i++) {
            for (int j = 0; j <= s2.size(); j++) {
                int cur = i + j - 1;
                if (i > 0 && s1[i - 1] != s3[cur]) dp[j] = false;
                if (j > 0 && s2[j - 1] == s3[cur]) dp[j] = dp[j] || dp[j - 1];
                
            }
        }
        return dp[s2.size()];
    }

    // bool dfs(int i1, int i2, int i3, const string & s1, const string & s2, const string & s3) {
    //     if (i3 == s3.size()) return true;
    //     if (i1 < s1.size() && i2 < s2.size() && s1[i1] == s3[i3] && s1[i1] == s2[i2]) return dfs(i1 + 1, i2, i3 + 1, s1, s2, s3) || dfs(i1, i2 + 1, i3 + 1, s1, s2, s3);
    //     if (i1 < s1.size() && s1[i1] == s3[i3]) return dfs(i1 + 1, i2, i3 + 1, s1, s2, s3);
    //     if (i2 < s2.size() && s2[i2] == s3[i3]) return dfs(i1, i2 + 1, i3 + 1, s1, s2, s3);
    //     return false;
    // }
};
// @lc code=end

